package com.dmall.directed.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SCC {

    private Graph G;
    private final int[] visited;
    private int scccount = 0;

    public SCC(Graph G) {
        if (!G.isDirected()) {
            throw new IllegalArgumentException("SCC only work in directed graph.");
        }
        this.G = G;
        this.visited = new int[G.V()];
        Arrays.fill(this.visited, -1);

        Graph reverseGraph = G.reverseGraph();
        GraphDFS dfs = new GraphDFS(reverseGraph);
        List<Integer> orders = new ArrayList<>(reverseGraph.V());
        for (int v : dfs.post()) {
            orders.add(v);
        }
        Collections.reverse(orders);

        for (int v : orders) {
            if (visited[v] == -1) {
                dfs(v, scccount);
                scccount ++;
            }
        }
    }

    private void dfs(int v, int sccid) {
        visited[v] = sccid;
        for (int w : G.adj(v)) {
            if (visited[w] == -1) {
                dfs(w, sccid);
            }
        }
    }

    public int count() {
        return scccount;
    }

    public boolean isStronglyCollected(int v, int w) {
        G.validateVertex(v);
        G.validateVertex(w);
        return visited[v] == visited[w];
    }

    public ArrayList<Integer>[] components() {
        ArrayList<Integer>[] components = new ArrayList[scccount];
        for (int sccid = 0; sccid < scccount; sccid++) {
            components[sccid] = new ArrayList<>();
        }
        for (int v = 0; v < G.V(); v++) {
            components[visited[v]].add(v);
        }
        return components;
    }

    public static void main(String[] args) {
        String filePath = SCC.class.getClassLoader().getResource("com/dmall/directed/graph/ug5.txt").getPath();
        Graph graph = new Graph(filePath, true);
        SCC scc = new SCC(graph);

        System.out.println(scc.count());

        ArrayList<Integer>[] components = scc.components();
        for (int sccid = 0; sccid < components.length; sccid ++) {
            System.out.print(sccid + " : ");
            for (int w : components[sccid]) {
                System.out.print(w + " ");
            }
            System.out.println();
        }
    }
}

















